package com.fr.lintcode;

public class Q63ii {


    /**
     * @param A: an integer ratated sorted array and duplicates are allowed
     * @param target: An integer
     * @return: a boolean 
     */
    public boolean search(int[] A, int target) {
        // write your code here
    	if (A == null) {
    		return false;
    	}
    	int mid = findMin(A);
    	boolean has = search(A, 0, mid, target);
    	if(!has) {
    		search(A, mid+1, A.length -1, target);
    	}
    	return false;
    }
    private boolean search(int[] A, int left, int right, int target) {
        while (left <= right) {
            int point = (left + right) / 2;
            if (A[point] > target) {
                right = point - 1;
            } else if (A[point] == target) {
                return true;
            } else {
                left = point + 1;
            }
        }
        return false;
    }
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int point = -1;
        while (left <= right) {
            point = (left + right) / 2;
            if (nums[left] > nums[right]) {// 旋转排序
                if (nums[point] >= nums[left]) {
                    left = point + 1;
                } else {
                    right = point;
                }
            } else {// 正确的排序
                return left;
            }

        }
        return point;
    }


}
